<?php
/**
 * @title 1025. 除数博弈
 * @author start2004
 */


class Solution {

    /**
     * @param Integer $N
     * @return Boolean
     */
    function divisorGame($N) {
        // if($N%2 == 0){
        if($N == ($N>>1)<<1){
            return true;
        } else {
            return false;
        }

        /**
         * @since 2020-07-24 每个数字结果
         */
        $dps = [
            1 => false,
        ];

        /**
         * @since 2020-07-24 穷列每个数
         */
        for($i=2; $i<=$N; $i++){
            $result = false;

            /**
             * @since 2020-07-24 满足能整除, 这个数最大是`i/2`
             */
            for($j=1; $j<=($i>>1); $j++){
                /**
                 * @since 2020-07-24 找到满足2个条件的获胜方案, break
                 */
                if($i%$j == 0){
                    /**
                     * @since 2020-07-24 `Alice`先手, 留下数字`i-j`, 要确保`Bob`必输
                     */
                    if($dps[$i-$j] === false){
                        $result = true;
                        break;
                    } else {}
                } else {}
            }
            $dps[$i] = $result;
        }

        /**
         * @return
         */
        return $dps[$N];
    }
}



/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.24.php
 */
$datas = [
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
    10,
    11,
    12,
    13,
    14,
    15,
    16,
    17,
    18,
    19,
    20,
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->divisorGame($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
